package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;


public class WordSearchII {

	// 找到words中在board中出现的所有字符串
	// 暴力超时
	public List<String> findWords(char[][] board, String[] words) {
		Set<String> list = new HashSet<String>();
		if (words == null || board == null) {
			return null;
		}

		WordSearch object = new WordSearch();
		for (String word : words) {
			if (object.exist(board, word)) {
				list.add(word);
			}
		}
		return new ArrayList<String>(list);
	}

	//前缀树的实现
	class TrieNode {
		public TrieNode[] children = new TrieNode[26];
		public String word = "";

		public TrieNode() {
		}
	}
	class Trie {
		private TrieNode root;

		public Trie() {
			root = new TrieNode();
		}

		// Inserts a word into the trie.
		public void insert(String word) {
			TrieNode node = root;
			for (char c : word.toCharArray()) {
				if (node.children[c - 'a'] == null) {
					node.children[c - 'a'] = new TrieNode();
				}
				node = node.children[c - 'a'];
			}
			node.word = word;
		}

		// Returns if the word is in the trie.
		public boolean search(String word) {
			TrieNode node = root;
			for (char c : word.toCharArray()) {
				if (node.children[c - 'a'] == null)
					return false;
				node = node.children[c - 'a'];
			}
			return node.word.equals(word);
		}

		// Returns if there is any word in the trie
		// that starts with the given prefix.
		public boolean startsWith(String prefix) {
			TrieNode node = root;
			for (char c : prefix.toCharArray()) {
				if (node.children[c - 'a'] == null)
					return false;
				node = node.children[c - 'a'];
			}
			return true;
		}
	}

	Set<String> res = new HashSet<String>();

	public List<String> findWords2(char[][] board, String[] words) {
		Trie trie = new Trie();
		for (String word : words) {
			trie.insert(word);
		}
		//不知道为什么，不用clear,可能是不同的对象调用，而且使用clear之后竟然超时
		//res.clear();
		int m = board.length;
		int n = board[0].length;
		boolean[][] visited = new boolean[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				dfs(board, visited, "", i, j, trie);
			}
		}

		return new ArrayList<String>(res);
	}

	public void dfs(char[][] board, boolean[][] visited, String str, int x,
			int y, Trie trie) {
		if (x < 0 || x >= board.length || y < 0 || y >= board[0].length)
			return;
		if (visited[x][y])
			return;

		str += board[x][y];
		//如果没有该前缀，那么直接返回
		if (!trie.startsWith(str))
			return;

		//如果有该单词
		if (trie.search(str)) {
			res.add(str);
		}

		visited[x][y] = true;
		dfs(board, visited, str, x - 1, y, trie);
		dfs(board, visited, str, x + 1, y, trie);
		dfs(board, visited, str, x, y - 1, trie);
		dfs(board, visited, str, x, y + 1, trie);
		visited[x][y] = false;
	}
	
	
	
	
	
	//concise the code
	
	public List<String> findWords3(char[][] board, String[] words) {
		Trie trie = new Trie();
		for (String word : words) {
			trie.insert(word);
		}
		TrieNode root = trie.root;
		int m = board.length;
		int n = board[0].length;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				dfs(board, i, j, root);
			}
		}
		return new ArrayList<String>(res);
	}
	
	public void dfs(char[][] board, int x,
			int y, TrieNode trie) {
		char c = board[x][y];
		if (x < 0 || x >= board.length || y < 0 || y >= board[0].length)
			return;
		if (board[x][y] == '#' || trie.children[c - 'a'] == null)
			return;

		trie = trie.children[c - 'a'];
		if (trie.word != null) {   // found one
	        res.add(trie.word);
	        
	        //the trie has ability of remove duplicate.
	        //while use this, we can use list directly rather than set
	        trie.word = null;     // de-duplicate
	    }
		
		board[x][y] = '#';
		if(x > 0)	dfs(board, x - 1, y, trie);
		if(x < board.length - 1)	dfs(board, x + 1, y, trie);
		if(y > 0)	dfs(board, x, y - 1, trie);
		if(x < board[0].length - 1)	dfs(board, x, y + 1, trie);
		board[x][y] = c;
	}
}
